package hot100;

import java.util.Random;

public class Solution912 {

    public int[] sortArray(int[] nums) {
        return nums;
    }


    public static void main(String[] args) {
        int[] nums = new int[]{7, 6, 5, 4, 3, 2, 1};
        QuickSort quickSort = new QuickSort();
        quickSort.quickSort(nums, 0, nums.length - 1);
    }
}

class QuickSort {

    private int randomIndex(int start, int end) {
        int index = new Random().nextInt(end - start + 1);
        return start + index;
    }

    private void swap(int[] nums, int index1, int index2) {
        int tmp = nums[index1];
        nums[index1] = nums[index2];
        nums[index2] = tmp;
    }

    private int partition(int[] nums, int start, int end) {
        if (start > end || nums == null) {
            return -1;
        }
        int small = start - 1;
        int index = randomIndex(start, end);
        swap(nums, end, index);
        for (int i = start; i < end; i++) {
            if (nums[i] < nums[end]) {
                small++;
                if (small != i) {
                    swap(nums, small, i);
                }
            }
        }
        small++;
        swap(nums, end, small);
        return small;
    }

    public void quickSort(int[] nums, int start, int end) {
        if (start >= end) {
            return;
        }
        int partition = partition(nums, start, end);
        quickSort(nums, start, partition - 1);
        quickSort(nums, partition + 1, end);
    }
}

class HeapSort {

    private void swap(int[] nums, int index1, int index2) {
        int tmp = nums[index1];
        nums[index1] = nums[index2];
        nums[index2] = tmp;
    }

    public void buildMaxHeap(int[] nums) {
        int end = nums.length - 1;
        for (int i = end / 2; i >= 0; i--) {
            downToHeap(nums, i, end);
        }
    }


    // 对下标为i的节点，将其构造为i的最大堆
    public void downToHeap(int[] nums, int i, int end) {
        while (i * 2 + 2 <= end) {
            int left = i * 2 + 1;
            int right = i * 2 + 2;
            int max;
            if (left <= end && nums[left] > nums[i]) {
                max = left;
            } else {
                max = i;
            }
            if (right <= end && nums[right] > nums[max]) {
                max = right;
            }
            if (max != i) {
                swap(nums, max, i);
                i = max;
            } else {
                break;
            }
        }
    }

    public void heapSort(int[] nums) {
        buildMaxHeap(nums);
        int end = nums.length - 1;
        for (int i = end; i >= 1; i--) {
            swap(nums, i, 0);
            end--;
            downToHeap(nums, 0, end);
        }
    }

    public static void main(String[] args) {
        HeapSort heapSort = new HeapSort();
        int[] nums = new int[]{7, 6, 5, 4, 3, 2, 1};
        heapSort.heapSort(nums);
    }

}

class MergeSort {

    int[] tmp;
    public int[] sortArray(int[] nums) {
        tmp = new int[nums.length];
        mergeSort(nums, 0, nums.length - 1);
        return nums;
    }

    private void mergeSort(int[] nums, int left, int right) {
        if (left >= right) {
            return;
        }
        int mid = (left + right) / 2;
        mergeSort(nums, left, mid);
        mergeSort(nums, mid + 1, right);
        int index = 0;
        int l = left;
        int r = mid + 1;
        while (l <= mid && r <= right) {
            if (nums[l] < nums[r]) {
                tmp[index++] = nums[l++];
            } else {
                tmp[index++] = nums[r++];
            }
        }
        while (l <= mid) {
            tmp[index++] = nums[l++];
        }
        while (r <= right) {
            tmp[index++] = nums[r++];
        }
        for (int i = 0; i < right - left + 1; i++) {
            nums[i + left] = tmp[i];
        }
    }
}
